#include <iostream>
#include <stack>
using namespace std;

struct TreeNode 
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x)
        : val(x)
        , left(NULL)
        , right(NULL) 
    {}
    TreeNode(int x, TreeNode* _left, TreeNode* _right)
        :val(x)
        , left(_left)
        , right(_right)
    {}
};
 
class Solution
{
public:
    TreeNode* ans;

    bool dfs(TreeNode* root, TreeNode* p, TreeNode* q)
    {
        if (root == nullptr)
            return false;
        bool lson = dfs(root->left, p, q);
        bool rson = dfs(root->right, p, q);
        if ((lson && rson) || ((lson || rson) && (root->val == p->val || root->val == q->val)))
        {
            ans = root;
        }
        return lson || rson || (root->val == p->val || root->val == q->val);
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
    {
        dfs(root, p, q);

        return ans;
    }
};

int main()
{
    TreeNode* I = new TreeNode(4);
    TreeNode* G = new TreeNode(7);
    TreeNode* F = new TreeNode(8);
    TreeNode* E = new TreeNode(0);
    TreeNode* D = new TreeNode(2, G, I);
    TreeNode* C = new TreeNode(6);
    TreeNode* B = new TreeNode(1, E, F);
    TreeNode* A = new TreeNode(5, C, D);
    TreeNode* root = new TreeNode(3, A, B);

    Solution xz;
    TreeNode* p = new TreeNode(5);
    TreeNode* q = new TreeNode(1);
    TreeNode* node = xz.lowestCommonAncestor(root, p, q);
    cout << node->val << endl;

	return 0;
}

